package twoD;

/**
 * @author pengfei.hpf
 * @date 2020/3/29
 * @verdion 1.0.0
 * 351. 安卓系统手势解锁
 * 我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。
 *
 * 给你两个整数，分别为 ​​m 和 n，其中 1 ≤ m ≤ n ≤ 9，那么请你统计一下有多少种解锁手势，是至少需要经过 m 个点，但是最多经过不超过 n 个点的。
 *
 *
 *
 * 先来了解下什么是一个有效的安卓解锁手势:
 *
 * 每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
 * 解锁手势里不能设置经过重复的点。
 * 假如手势中有两个点是顺序经过的，那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
 * 经过点的顺序不同则表示为不同的解锁手势。
 *
 *
 *
 *
 *
 * 解释:
 *
 * | 1 | 2 | 3 |
 * | 4 | 5 | 6 |
 * | 7 | 8 | 9 |
 * 无效手势：4 - 1 - 3 - 6
 * 连接点 1 和点 3 时经过了未被连接过的 2 号点。
 *
 * 无效手势：4 - 1 - 9 - 2
 * 连接点 1 和点 9 时经过了未被连接过的 5 号点。
 *
 * 有效手势：2 - 4 - 1 - 3 - 6
 * 连接点 1 和点 3 是有效的，因为虽然它经过了点 2 ，但是点 2 在该手势中之前已经被连过了。
 *
 * 有效手势：6 - 5 - 4 - 1 - 9 - 2
 * 连接点 1 和点 9 是有效的，因为虽然它经过了按键 5 ，但是点 5 在该手势中之前已经被连过了。
 *
 *
 *
 * 示例:
 *
 * 输入: m = 1，n = 1
 * 输出: 9
 */
public class NumberOfPatterns {

    public int numberOfPatterns(int m, int n) {
        if(m <= 0 && n <= 0){
            return 0;
        }
        boolean[][] visited = new boolean[3][3];
        return dfs(0,0, visited, 0, m, n) * 4 + dfs(0,1, visited, 0, m, n) * 4 + dfs(1,1, visited, 0, m, n);
    }

    private  boolean canVisited(int x1, int y1, int x2, int y2, boolean[][] visited){
        if(visited[x2][y2]){
            return false;
        }
        if (Math.abs(x1 - x2) <= 1 && Math.abs(y1 - y2) <= 1) {
            return true;
        }
        if (Math.abs(x1 - x2) != 1 && Math.abs(y1 - y2) != 1) {
            return visited[(x1 + x2) / 2][(y1 + y2) / 2];
        }
        return true;
    }

    private int dfs(int x, int y, boolean[][] visited, int count, int m, int n){
        int res = 0;
        count ++;
        if(count >= m){
            res ++;
        }
        if(count == n){
            return res;
        }
        visited[x][y] = true;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j ++){
                if(canVisited(x, y, i, j, visited)){
                    res += dfs(i, j, visited, count, m, n);
                }
            }
        }
        visited[x][y] = false;
        return res;
    }
}
